package string;

/*
    Given two binary strings, return their sum (also a binary string).

    The input strings are both non-empty and contains only characters 1 or 0.

    Example 1:

        Input: a = "11", b = "1"
        Output: "100"

    Example 2:

        Input: a = "1010", b = "1011"
        Output: "10101"
 */
public class BinaryAdd {


    public String addBinary1(String a, String b) {

        StringBuilder sb = new StringBuilder();

        String longer; //较长的字符串
        String shorter; //较短的字符串
        if(a.length()>=b.length()){
            longer = a;
            shorter = b;
        }else {
            longer = b;
            shorter = a;
        }

        int longerFlag = longer.length();
        int shorterFlag = shorter.length();

        boolean plusFlag = false;//进一标识，初始为 false
        boolean addPosition = false; //增位标识，初始为 false

        while (longerFlag > 0){

            char l = longer.charAt(longerFlag - 1);//长字符串最低位的字符

            if(shorterFlag>0){
                char s = shorter.charAt(shorterFlag - 1);//短字符串最低位的字符
                if(plusFlag){ //字符计算+进一
                    if(longerFlag==1){
                        addPosition = true;
                    }
                    if(l=='0' && s=='0'){
                        plusFlag = false; //进一时都是0时不进位，改变进一标识
                        sb.append("1");
                    }else if(l=='1' && s=='1'){
                        sb.append("1");
                    }else {
                        sb.append("0");
                    }

                }else { //字符计算
                    if(l=='1' && s=='1'){
                        plusFlag = true; //不进一时都是0时进位，改变进一标识
                        if(longerFlag==1){
                            addPosition = true;//字符串等长时增位
                        }
                        sb.append("0");
                    }else if(l=='0' && s=='0'){
                        sb.append("0");
                    }else {
                        sb.append("1");
                    }
                }
                shorterFlag--;//短字符串每次计算（循环）次数减一
            }else{
                //长字符串剩余字符（比短字符多出的部分）的计算
                if(plusFlag){
                    if(longerFlag==1){
                        addPosition = true;//到最高位时进一标识为true,则增位
                        sb.append(0);
                    }else {
                        if(l=='0'){
                            plusFlag = false;
                            sb.append("1");
                        }else {
                            sb.append("0");
                        }
                    }
                }else {
                    sb.append(l);
                }
            }

            if(addPosition){
                sb.append("1");
            }

            longerFlag--;//长字符串每次计算（循环）次数减一
        }

        return sb.reverse().toString();
    }

    /**
     * 解题思路，高位补零
     */
    public String addBinary2(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int ca = 0;
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
            int sum = ca;
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            ans.append(sum % 2);
            ca = sum / 2;
        }
        ans.append(ca == 1 ? ca : "");
        return ans.reverse().toString();
    }


}
